package leetcode_动态规划._07背包问题._01背包;

/**
 * @author yzh
 * @data 2021/3/18 13:50
 * 分割等和子集
 * 思路：
 *   数组中的和为偶数才能分割，先排除奇数
 *   转化成 01 背包，每次取一个数
 */
public class _416 {

    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int i : nums)  sum += i;
        if (sum % 2 != 0) return false;
        sum >>= 1;
        int[] dp = new int[sum + 1];
        for (int i = 0; i < nums.length; i++) {
            for (int j = sum; j >= nums[i]; --j) {
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        return dp[sum] == sum;
    }
}
